//
// Created by tianq on 24-12-9.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
using namespace std;

int main() {
    int n = 0;
    vector<int> numbers;

    // cin >> n;
    // for (int i = 0; i < n; i++) {
    //     int tmp;
    //     cin >> tmp;
    //     numbers.push_back(tmp);
    // }

    n = 6;
    random_device rd;
    mt19937_64 rng(rd());
    uniform_int_distribution dist(1, 20); // set range for random generator here
    for (int i = 0; i < n; i++) {
        numbers.emplace_back(dist(rng));
    }

    cout << n << endl;
    for (const int &number : numbers) {
        cout << number << ' ';
    }
    cout << endl;

    // ideology
    // by merging smallest 2 each time, we get the biggest one
    // by merging greatest 2 each time, we get the smallest one
    // don't just take my words, try it on paper

    vector<int> maxNums = numbers, minNums = numbers;

    ranges::sort(maxNums);
    while (maxNums.size() > 1) {
        int newNum = maxNums[0] * maxNums[1] + 1;
        maxNums.erase(maxNums.begin(), maxNums.begin() + 2);
        auto it = ranges::lower_bound(maxNums, newNum);
        maxNums.emplace(it, newNum);

        for (const int &number : maxNums) {
            cout << number << ' ';
        }
        cout << endl;
    }

    ranges::sort(minNums, greater());
    while (minNums.size() > 1) {
        int newNum = minNums[0] * minNums[1] + 1;
        minNums.erase(minNums.begin(), minNums.begin()+2);
        // the product of two biggest numbers should still be biggest
        minNums.emplace(minNums.begin(), newNum);

        for (const int &number : minNums) {
            cout << number << ' ';
        }
        cout << endl;
    }

    cout << "Max: " << maxNums[0] << ", Min: " << minNums[0] << endl;
    cout << "M: " << maxNums[0] - minNums[0] << endl;

}

